home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / lib / c / bit / bitInt.h < prev    next >
C/C++ Source or Header  |  1988-06-19  |  4KB  |  192 lines
  1. /*
  2.  * bitInt.h --
  3.  *
  4.  *    Definitions used internally by the bit routines, but not
  5.  *    exported to the outside world.
  6.  *
  7.  * Copyright 1988 Regents of the University of California
  8.  * Permission to use, copy, modify, and distribute this
  9.  * software and its documentation for any purpose and without
  10.  * fee is hereby granted, provided that the above copyright
  11.  * notice appear in all copies.  The University of California
  12.  * makes no representations about the suitability of this
  13.  * software for any purpose.  It is provided "as is" without
  14.  * express or implied warranty.
  15.  *
  16.  * $Header: bitInt.h,v 1.1 88/06/19 14:34:53 ouster Exp $ SPRITE (Berkeley)
  17.  */
  18.  
  19. #ifndef _BITINT
  20. #define _BITINT
  21.  
  22. /*
  23.  * The Bit_FindFirst* routines use a binary search algorithm. Compared with
  24.  * a simple iteration algorithm, the algorithm used below is better because
  25.  * 1) the average execution time is about 10% less.
  26.  * 2) the execution time is relatively independent of the position of 
  27.  *    the bit in the integer. Iteration excution time is proportional to
  28.  *    the bit position.
  29.  *
  30.  * The two Bit_FindFirst* routines use the same basic algorithm. Two macros, 
  31.  * QUICK_TEST and TEST have different definitions depending on the routine.
  32.  *
  33.  * The QUICK_TEST at the top of the loop tests "temp" to see if it needs to be
  34.  * searched. If QUICK_TEST is true, then at least 1 bit is set/cleared in temp.
  35.  * The basic algorithm is "see if that bit is in the right half otherwise it 
  36.  * must be in the left half". 
  37.  */
  38.  
  39. #define SET_QUICK_TEST        if (temp != 0) 
  40. #define CLEAR_QUICK_TEST    if (temp != ~0) 
  41.  
  42. #define SET_TEST(mask)        if ((temp & (mask)) != 0) 
  43. #define CLEAR_TEST(mask)    if ((temp & (mask)) != (mask)) 
  44.  
  45. /*
  46.  * RETURN returns the index of the first bit that is set/cleared in the
  47.  * intNum integer in the array.
  48.  */
  49. #define RETURN(num)     return((intNum*BIT_NUM_BITS_PER_INT)+num);
  50.  
  51. #define FIND_FIRST(numBits, arrayPtr) { \
  52.     register int numInts = Bit_NumInts(numBits); \
  53.     register int temp, intNum; \
  54.     for (intNum = 0; intNum < numInts; intNum++, arrayPtr++) { \
  55.     temp = *arrayPtr; \
  56.     QUICK_TEST { \
  57.         TEST(0x0000ffff) { \
  58.         TEST(0x000000ff) { \
  59.             TEST(0x0000000f) { \
  60.             TEST(0x00000003) { \
  61.                 TEST(0x00000001) { \
  62.                 RETURN(0); \
  63.                 } else { \
  64.                 RETURN(1); \
  65.                 } \
  66.             } else { \
  67.                 TEST(0x00000004) { \
  68.                 RETURN(2); \
  69.                 } else { \
  70.                 RETURN(3); \
  71.                 } \
  72.             } \
  73.             } else { \
  74.             TEST(0x00000030) { \
  75.                 TEST(0x00000010) { \
  76.                 RETURN(4); \
  77.                 } else { \
  78.                 RETURN(5); \
  79.                 } \
  80.             } else { \
  81.                 TEST(0x00000040) { \
  82.                 RETURN(6); \
  83.                 } else { \
  84.                 RETURN(7); \
  85.                 } \
  86.             } \
  87.             } \
  88.         } else { \
  89.             TEST(0x00000f00) { \
  90.             TEST(0x00000300) { \
  91.                 TEST(0x00000100) { \
  92.                 RETURN(8); \
  93.                 } else { \
  94.                 RETURN(9); \
  95.                 } \
  96.             } else { \
  97.                 TEST(0x00000400) { \
  98.                 RETURN(10); \
  99.                 } else { \
  100.                 RETURN(11); \
  101.                 } \
  102.             } \
  103.             } else { \
  104.             TEST(0x00003000) { \
  105.                 TEST(0x00001000) { \
  106.                 RETURN(12); \
  107.                 } else { \
  108.                 RETURN(13); \
  109.                 } \
  110.             } else { \
  111.                 TEST(0x00004000) { \
  112.                 RETURN(14); \
  113.                 } else { \
  114.                 RETURN(15); \
  115.                 } \
  116.             } \
  117.             } \
  118.         } \
  119.         } else { \
  120.         TEST(0x00ff0000) {  \
  121.             TEST(0x000f0000) { \
  122.             TEST(0x00030000) { \
  123.                 TEST(0x00010000) { \
  124.                 RETURN(16); \
  125.                 } else { \
  126.                 RETURN(17); \
  127.                 } \
  128.             } else { \
  129.                 TEST(0x00040000) { \
  130.                 RETURN(18); \
  131.                 } else { \
  132.                 RETURN(19); \
  133.                 } \
  134.             } \
  135.             } else { \
  136.             TEST(0x00300000) { \
  137.                 TEST(0x00100000) { \
  138.                 RETURN(20); \
  139.                 } else { \
  140.                 RETURN(21); \
  141.                 } \
  142.             } else { \
  143.                 TEST(0x00400000) { \
  144.                 RETURN(22); \
  145.                 } else { \
  146.                 RETURN(23); \
  147.                 } \
  148.             } \
  149.             } \
  150.         } else { \
  151.             TEST(0x0f000000) { \
  152.             TEST(0x03000000) { \
  153.                 TEST(0x01000000) { \
  154.                 RETURN(24); \
  155.                 } else { \
  156.                 RETURN(25); \
  157.                 } \
  158.             } else { \
  159.                 TEST(0x04000000) { \
  160.                 RETURN(26); \
  161.                 } else { \
  162.                 RETURN(27); \
  163.                 } \
  164.             } \
  165.             } else { \
  166.             TEST(0x30000000) { \
  167.                 TEST(0x10000000) { \
  168.                 RETURN(28); \
  169.                 } else { \
  170.                 RETURN(29); \
  171.                 } \
  172.             } else { \
  173.                 TEST(0x40000000) { \
  174.                 RETURN(30); \
  175.                 } else { \
  176.                 RETURN(31); \
  177.                 } \
  178.             } \
  179.             } \
  180.         } \
  181.         } \
  182.     } \
  183.     } \
  184.     return(-1); \
  185. }
  186.  
  187. #define GET_MASK_AND_INTS(nB,i,m) \
  188.      i = (nB) / BIT_NUM_BITS_PER_INT; \
  189.     m = ((1 << ((nB) % BIT_NUM_BITS_PER_INT)) - 1)
  190.  
  191. #endif _BITINT
  192.